home *** CD-ROM | disk | FTP | other *** search
/ The X-Philes (2nd Revision) / The X-Philes Number 1 (1995).iso / xphiles / hp48_2 / vsrc.tar / voyager7_src / tree.c < prev    next >
C/C++ Source or Header  |  1991-02-27  |  7KB  |  413 lines
  1. /*
  2. // Abstract:
  3. //    TREE---Balanced Binary Tree Routines
  4. //
  5. //    The Balanced Binary Tree Routines module contains routines for
  6. //    handling Balanced Binary Trees.
  7. //
  8. //    See The Art of Computer Programming / Volume 3 / Searching and
  9. //    Sorting, Donald E. Knuth, pp 451-457.
  10. //
  11. // Author:
  12. //    Derek S. Nickel
  13. //
  14. // Creation date:
  15. //    11 November 1990
  16. //
  17. // History:
  18. // V01-001    Derek S. Nickel        11-NOV-1990
  19. //    Original.
  20. //
  21. */
  22.  
  23. #include <stddef.h>
  24. #include <stdio.h>
  25.  
  26. #pragma check_stack+
  27.  
  28. typedef unsigned long cond_value;
  29. typedef unsigned long mask_longword;
  30.  
  31. const cond_value lib$_normal = 0x00000001;
  32. const cond_value lib$_keyalrins = 0x00158021;
  33. const cond_value lib$_keynotfou = 0x001582FC;
  34.  
  35. typedef struct _inode_t inode_t;
  36.  
  37. struct _inode_t {
  38.     inode_t *llink;
  39.     inode_t *rlink;
  40.     short b;
  41. };
  42.  
  43. #define LLINK(P) (P)->llink
  44. #define RLINK(P) (P)->rlink
  45. #define B(P) (P)->b
  46.  
  47. //#define TRACE(txt) printf("Trace: %s\n",txt)
  48. #define TRACE(txt)
  49.  
  50. /***********************************************************************
  51.     insert_tree
  52. ***********************************************************************/
  53.  
  54. cond_value insert_tree(
  55.     inode_t **treehead,
  56.     void *K,
  57.     mask_longword *flags,
  58.     int (*compare_rtn)(),
  59.     int (*allocate_rtn)(),
  60.     void **new_node,
  61.     void *user_data )
  62. {
  63.     inode_t *P;
  64.     inode_t *Q;
  65.     inode_t *R;
  66.     inode_t *S;
  67.     inode_t *T;
  68.     int a;
  69.     int cmp;
  70.  
  71.     /*
  72.     // A0. [New tree?]
  73.     */
  74.  
  75.     if (*treehead == NULL) {
  76.         TRACE("new binary tree");
  77.         (*allocate_rtn)(K,treehead,user_data);
  78.         LLINK(*treehead) = RLINK(*treehead) = NULL;
  79.         B(*treehead) = 0;
  80.         *new_node = *treehead;
  81.         return lib$_normal;
  82.     }
  83.  
  84.     /*
  85.     // A1. [Initialize.] (The pointer variable P will move down the
  86.     // tree; S will point to the place where rebalancing may be
  87.     // necessary, and T always points to the father of S.
  88.     */
  89.  
  90.     T = (inode_t *)treehead;
  91.     S = P = *treehead;
  92.  
  93.     /*
  94.     // A2. [Compare.]
  95.     */
  96. A2:
  97.     cmp = (*compare_rtn)(K,&P);
  98.     if (cmp < 0) {
  99.         /*
  100.         // A3. [Move left.]
  101.         */
  102.  
  103.         Q = LLINK(P);
  104.         if (Q == NULL) {
  105.             (*allocate_rtn)(K,&Q,user_data);
  106.             LLINK(P) = Q;
  107.             goto A5;
  108.         } else {
  109.             if (B(Q) != 0) {
  110.                 T = P;
  111.                 S = Q;
  112.             }
  113.             P = Q;
  114.             goto A2;
  115.         }
  116.  
  117.     } else if (cmp > 0) {
  118.         /*
  119.         // A4. [Move right.]
  120.         */
  121.  
  122.         Q = RLINK(P);
  123.  
  124.         if (Q == NULL) {
  125.             cmp = (*allocate_rtn)(K,&Q,user_data);
  126.             RLINK(P) = Q;
  127.             goto A5;
  128.         } else {
  129.             if (B(Q) != 0) {
  130.                 T = P;
  131.                 S = Q;
  132.             }
  133.             P = Q;
  134.             goto A2;
  135.         }
  136.     } else {
  137.         *new_node = P;
  138.         return lib$_keyalrins;
  139.     }
  140.  
  141.     /*
  142.     // A5. [Insert.]  (We have just linked a new node, NODE(Q), into
  143.     // the tree and its fields need to be initialized.
  144.     */
  145. A5:
  146.     /* KEY(Q) = K; - done by allocate routine */
  147.     LLINK(Q) = RLINK(Q) = NULL;
  148.     B(Q) = 0;
  149.     *new_node = Q;
  150.  
  151.     /*
  152.     // A6. [Adjust balance factors.]  (Now that the balance factors
  153.     // on the nodes between A and Q need to be changed from zero to
  154.     // +/- one.)
  155.     */
  156.  
  157.     cmp = (*compare_rtn)(K,&S);
  158.     if (cmp < 0)
  159.         R = P = LLINK(S);
  160.     else
  161.         R = P = RLINK(S);
  162.  
  163.     while (P != Q) {
  164.         cmp = (*compare_rtn)(K,&P);
  165.         if (cmp < 0) {
  166.             B(P) = -1;
  167.             P = LLINK(P);
  168.         } else if (cmp > 0) {
  169.             B(P) = +1;
  170.             P = RLINK(P);
  171.         }
  172.     }
  173.  
  174.     /*
  175.     // A7. [Balancing act.]
  176.     */
  177.  
  178.     cmp = (*compare_rtn)(K,&S);
  179.     if (cmp < 0) a = -1;
  180.     else a = 1;
  181.  
  182.     if (B(S) == 0) {
  183.         /*
  184.         // i) the tree has grown higher.
  185.         */
  186.  
  187.         B(S) = a;
  188.         return lib$_normal;
  189.  
  190.     } else if (B(S) == -a) {
  191.         /*
  192.         // ii) the tree has gotten more balanced.
  193.         */
  194.  
  195.         B(S) = 0;
  196.         return lib$_normal;
  197.  
  198.     } else if (B(S) == a) {
  199.         /*
  200.         // iii) the tree has gotton out of balance.
  201.         */
  202.  
  203.         if (B(R) == a)
  204.             goto A8;
  205.         else if (B(R) == -a)
  206.             goto A9;
  207.     }
  208.  
  209.     /*
  210.     // A8. [Single rotation.]
  211.     */
  212. A8:
  213.     TRACE("Single rotation");
  214.     P = R;
  215.  
  216.     if (a == 1) {
  217.         RLINK(S) = LLINK(R);
  218.         LLINK(R) = S;
  219.  
  220.     } else {
  221.         LLINK(S) = RLINK(R);
  222.         RLINK(R) = S;
  223.     }
  224.  
  225.     B(S) = B(R) = 0;
  226.     goto A10;
  227.  
  228.     /*
  229.     // A9. [Double rotation.]
  230.     */
  231. A9:
  232.     TRACE("Double rotation");
  233.     if (a == 1) {
  234.         P = LLINK(R);
  235.         LLINK(R) = RLINK(P);
  236.         RLINK(P) = R;
  237.         RLINK(S) = LLINK(P);
  238.         LLINK(P) = S;
  239.  
  240.     } else {
  241.         P = RLINK(R);
  242.         RLINK(R) = LLINK(P);
  243.         LLINK(P) = R;
  244.         LLINK(S) = RLINK(P);
  245.         RLINK(P) = S;
  246.     }
  247.  
  248.     if (B(P) == a) {
  249.         B(S) = -a;
  250.         B(R) = 0;
  251.     } else if (B(P) == 0) {
  252.         B(S) = 0;
  253.         B(R) = 0;
  254.     } else if (B(P) == -a) {
  255.         B(S) = 0;
  256.         B(R) = a;
  257.     }
  258.  
  259.     B(P) = 0;
  260.     goto A10;
  261.  
  262.     /*
  263.     // A10. [Finishing touch.]  We have completed the rebalancing
  264.     // trasformation, taking (1) to (2) (see KNUTH), with P pointing
  265.     // to the new root and T pointing to the father of the old root.
  266.     */
  267. A10:
  268.     if (S == RLINK(T))
  269.         RLINK(T) = P;
  270.     else
  271.         LLINK(T) = P;
  272.  
  273.     return lib$_normal;
  274. }
  275.  
  276. /***********************************************************************
  277.     lookup_tree
  278. ***********************************************************************/
  279.  
  280. cond_value lookup_tree(
  281.     inode_t **treehead,
  282.     void *K,
  283.     int (*compare_rtn)(),
  284.     inode_t **new_node )
  285. {
  286.     inode_t *node;
  287.     int cmp;
  288.  
  289.     node = *treehead;
  290.  
  291.     while (node != NULL) {
  292.  
  293.         cmp = (*compare_rtn)(K,&node);
  294.  
  295.         if (cmp < 0)
  296.             node = node->llink;
  297.         else if (cmp > 0)
  298.             node = node->rlink;
  299.         else {
  300.             *new_node = node;
  301.             return lib$_normal;
  302.         }
  303.     }
  304.  
  305.     *new_node = NULL;
  306.     return lib$_keynotfou;
  307.  
  308. }
  309.  
  310. /***********************************************************************
  311.     preorder_traversal
  312. ***********************************************************************/
  313.  
  314. static cond_value preorder_traversal(
  315.     inode_t **treehead,
  316.     int (*action_rtn)(),
  317.     void *user_data )
  318. {
  319.     inode_t *node;
  320.  
  321.     node = *treehead;
  322.  
  323.     (*action_rtn)(node,user_data);
  324.  
  325.     if (node->llink != NULL)
  326.         preorder_traversal(&node->llink,action_rtn,user_data);
  327.  
  328.     if (node->rlink != NULL)
  329.         preorder_traversal(&node->rlink,action_rtn,user_data);
  330.  
  331.     return lib$_normal;
  332. }
  333.  
  334. /***********************************************************************
  335.     inorder_traversal
  336. ***********************************************************************/
  337.  
  338. static cond_value inorder_traversal(
  339.     inode_t **treehead,
  340.     int (*action_rtn)(),
  341.     void *user_data )
  342. {
  343.     inode_t *node;
  344.  
  345.     node = *treehead;
  346.  
  347.     if (node->llink != NULL)
  348.         inorder_traversal(&node->llink,action_rtn,user_data);
  349.  
  350.     (*action_rtn)(node,user_data);
  351.  
  352.     if (node->rlink != NULL)
  353.         inorder_traversal(&node->rlink,action_rtn,user_data);
  354.  
  355.     return lib$_normal;
  356. }
  357.  
  358. /***********************************************************************
  359.     postorder_traversal
  360. ***********************************************************************/
  361.  
  362. static cond_value postorder_traversal(
  363.     inode_t **treehead,
  364.     int (*action_rtn)(),
  365.     void *user_data )
  366. {
  367.     inode_t *node;
  368.  
  369.     node = *treehead;
  370.  
  371.     if (node->llink != NULL)
  372.         postorder_traversal(&node->llink,action_rtn,user_data);
  373.  
  374.     if (node->rlink != NULL)
  375.         postorder_traversal(&node->rlink,action_rtn,user_data);
  376.  
  377.     (*action_rtn)(node,user_data);
  378.  
  379.     return lib$_normal;
  380. }
  381.  
  382. /***********************************************************************
  383.     traverse_tree
  384. ***********************************************************************/
  385.  
  386. cond_value traverse_tree(
  387.     inode_t **treehead,
  388.     int (*action_rtn)(),
  389.     void *user_data )
  390. {
  391.     if (*treehead == NULL) {
  392.         return lib$_normal;
  393.     } else {
  394.         return inorder_traversal(treehead,action_rtn,user_data);
  395.     }
  396. }
  397.  
  398. /***********************************************************************
  399.     post_order_traversal
  400. ***********************************************************************/
  401.  
  402. cond_value post_order_traversal(
  403.     inode_t **treehead,
  404.     int (*action_rtn)(),
  405.     void *user_data )
  406. {
  407.     if (*treehead == NULL) {
  408.         return lib$_normal;
  409.     } else {
  410.         return postorder_traversal(treehead,action_rtn,user_data);
  411.     }
  412. }
  413.